`
https://leetcode.cn/problems/matrix-block-sum/
`

/**
 * @param {number[][]} mat
 * @param {number} k
 * @return {number[][]}
 */
var matrixBlockSum = function (mat, k) {
  const m = mat.length, n = mat[0].length

  const prefixSum = new NumMatrix(mat)

  const res = new Array(m).fill(null).map(() => new Array(n).fill(0))

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const
        // 左上角坐标
        x1 = Math.max(i - k, 0),
        y1 = Math.max(j - k, 0),
        // 右上角坐标
        x2 = Math.min(i + k, m - 1),
        y2 = Math.min(j + k, n - 1)
      res[i][j] = prefixSum.sumRegion(x1, y1, x2, y2)
    }
  }

  return res
};

class NumMatrix {
  constructor(matrix) {
    const m = matrix.length, n = matrix[0].length
    const preSum = new Array(m + 1).fill(null).map(() => new Array(n + 1).fill(0))
    for (let i = 1; i <= m; i++) {
      for (let j = 1; j <= n; j++) {
        preSum[i][j] = matrix[i - 1][j - 1] + preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1]
      }
    }
    this.preSum = preSum
  }
  sumRegion(row1, col1, row2, col2) {
    return this.preSum[row2 + 1][col2 + 1] - this.preSum[row2 + 1][col1] - this.preSum[row1][col2 + 1] + this.preSum[row1][col1]
  }
}
